A software program (i.e., program) is a set of computer instructions executed by a computing device that directs the operation of the computing device to enable the computing device to provide useful functions. The computer instructions in the program are executed by computing resources provided by the central processing unit (CPU) of the computing device, i.e., CPU resources. Those skilled in the art will appreciate that CPU resources are often provided by, for example, a microprocessor but may be provided by a plurality of microprocessors or by an equivalent device, devices, device set, or device sets.
In a simple computing device, e.g., a digital clock, one program or a small set of interacting programs is sufficient to direct the operation of the computing device. A more complex computing device, e.g., a microwave oven, requires the coordinated activities of a plurality of programs. A common way to coordinate the activities of a plurality of programs executed by a computing device is to use another program to control the programs. A program that is executed by a computing device to coordinate the activities of other programs executed by the computing device is called an operating system. A computing device executes an operating system. An operating system controls programs executed by the computing device.
There are special purpose, i.e., dedicated, operating systems and general purpose operating systems. A dedicated operating system provides a narrow range of functions to a computing device with a bounded and well-defined purpose, e.g., an automatic dishwasher. A general purpose operating system provides a wide range of functions to a computing device with a wide range of purposes, e.g., a desktop computer. Certain dedicated operating systems are more narrowly classified as real-time operating systems. A real-time operating system can be used in applications where the computing device must respond in a limited amount of time and in a predictable way. For example, an avionic guidance system must precisely adjust the control services of a jet aircraft in microseconds to keep the aircraft flying.
While it is true that the CPU resources of a computing device execute the computer instructions in a program, it is more precise to say that the CPU resources execute the computer instructions in an instance of the program, i.e., a program instance. A program instance is to the program from which it was instantiated as a performance of music is to the musical score that is played. More than one instance of a program may be executed by an operating system. For example, three program instances of the same video playback program may be executed by the operating system of one computing device. All three instances of the video playback program may execute the computer instructions of the video playback program but each instance plays a different video clip in a graphical user interface component associated with the specific program instance and the specific video clip. An example of a type of graphical user interface component that may be used to play a video clip is a “window.” A window is a bounded portion of a graphical user interface display surface dedicated to a particular application or function.
In an operating system, an instance of a program is referred to as a “process” and the data representing a process is stored in a data structure, e.g., a “process block.” A process block contains data structures and pointers to data structures containing data related to the process. In the above example of the three video playback program instances, i.e., processes, there are three process blocks, one each for each process. Among other items, a process contains threads of execution, i.e., threads. When executing, a thread provides one or more of the activities of a process. For example, in a video playback process, one thread may play the video while another thread accepts inputs from user controls. Each thread in a process is represented by a data structure, e.g., a “thread block,” that is stored in the process block or pointed to by a pointer in the process block.
A typical computing device appears to execute thousands of threads simultaneously using CPU resources that execute a relatively small number of threads at any one time. The operating system enables a computing device to simulate the simultaneous execution of threads by periodically giving each thread access to CPU resources. The operating system schedules when and for how long each thread uses CPU resources so that each thread can keep up with the demands of the thread's task. Certain threads have higher demands than other threads. For example, a thread that renders image frames of a video clip to a display has higher demands than a thread waiting for incoming e-mail messages. While the e-mail message thread can check for messages every few seconds, the video rendering thread must render each image frame to the display quickly enough to keep the video clip running smoothly. It is critical that the video rendering thread get access to CPU resources quickly and more often than the e-mail thread. The video rendering thread is an example of a time-sensitive thread and the e-mail thread is an example of a time-insensitive thread.
In a general purpose operating system, to increase the probability that the time-sensitive threads get access to CPU resources quickly and more often than time-insensitive threads, time-sensitive threads are given a higher “priority” than time-insensitive threads. A priority is an integer value within a small range of integer values, for example, 0 to 31. Threads that have higher values have higher priority and have a higher probability of getting access to CPU resources quickly and often. The scheme by which an operating system determines priorities is called a priority scheme. In the prior art, priority schemes in most general purpose operating systems work well for threads in most processes; however, threads in multimedia processes, e.g., video playback, often overwhelm priority schemes of general purpose operating systems. For example, if an e-mail process needs to respond to incoming messages while a video playback process is playing a video, the video image may freeze or deteriorate. To avoid such behavior, multimedia processes require a computing device using a general purpose operating system to respond quickly, i.e., imitate the response of real-time operating systems.
In order to achieve performance similar to a real-time operating system and ensure that videos play smoothly, a general purpose operating system may set the priority of video playback processes to a high available level. However, this approach may cause the video playback processes to use CPU resources so often that lower priority processes do not get access to CPU resources quickly enough to keep up with the demands of the tasks of the lower priority processes. For example, if video playback processes are given the highest priority, an e-mail process may be unable to accept incoming messages while videos are playing.
The foregoing discussion demonstrates a clear need to enable a general purpose operating system to ensure that time-sensitive threads, e.g., multimedia threads, have a high probability of gaining access to CPU resources quickly enough to meet the demands of time-sensitive tasks while allowing time-insensitive threads to meet the demands of time-insensitive tasks. The present invention is directed to fulfilling this need.